Computational Complexity Classes: Definitions, Inclusions, and Open Problems

1. Introduction

Computational complexity theory studies the resources required to solve computational problems, particularly time (the number of computational steps) and space (the amount of memory used). Problems are grouped into complexity classes according to the resources needed by algorithms that solve them.

One of the central results in complexity theory is the following hierarchy:

P \subseteq N P \subseteq P S P A C E \subseteq E X P T I M E \subseteq E X P S P A C E

Although every inclusion is mathematically established, whether all of them are strict remains unknown.

2. Definitions of the Complexity Classes

P — Polynomial Time

P is the class of decision problems solvable by a deterministic Turing machine in polynomial time.

P = ⋃_{k \geq 1} D T I M E (n^{k})

Examples include graph connectivity, shortest-path decision problems, and primality testing.

Problems in P are conventionally considered computationally tractable.

NP — Nondeterministic Polynomial Time

NP is the class of decision problems for which a proposed solution can be verified in polynomial time by a deterministic algorithm.

N P = ⋃_{k \geq 1} N T I M E (n^{k})

Examples include Boolean satisfiability (SAT), Hamiltonian cycle, and the traveling salesperson decision problem.

Every problem in P also belongs to NP because a problem that can be solved efficiently can also be verified efficiently.

Whether (\mathrm{P}=\mathrm{NP}) remains one of the most important open questions in mathematics and computer science.

PSPACE — Polynomial Space

PSPACE contains decision problems solvable by deterministic algorithms using polynomial memory, regardless of execution time.

P S P A C E = ⋃_{k \geq 1} D S P A C E (n^{k})

A canonical PSPACE-complete problem is the True Quantified Boolean Formula problem (TQBF).

By Savitch's theorem, nondeterministic polynomial space provides no additional computational power:

P S P A C E = N P S P A C E

It remains unknown whether NP is strictly contained in PSPACE.

EXPTIME — Exponential Time

EXPTIME, also called EXP, contains decision problems solvable by deterministic algorithms in exponential time with a polynomial exponent.

E X P T I M E = ⋃_{k \geq 1} D T I M E (2^{n^{k}})

Examples include generalized chess on suitably encoded boards and certain computational games.

Unlike P versus NP, the deterministic Time Hierarchy Theorem establishes that:

P ⊊ E X P T I M E

Thus, some problems provably require more than polynomial time.

EXPSPACE — Exponential Space

EXPSPACE contains decision problems solvable by deterministic algorithms using at most exponential space with a polynomial exponent.

E X P S P A C E = ⋃_{k \geq 1} D S P A C E (2^{n^{k}})

An example of an EXPSPACE-complete problem is the equivalence problem for regular expressions extended with a squaring operation.

The deterministic Space Hierarchy Theorem establishes:

P S P A C E ⊊ E X P S P A C E

This separation is unconditional and mathematically proven.

3. Inclusions and Separations

The hierarchy follows from fundamental properties of deterministic and nondeterministic computation.

Relationship	Status	Mathematical basis
P ⊆ NP	Proven	Deterministic computation is a special case of nondeterminism
NP ⊆ PSPACE	Proven	Polynomial-time computations use at most polynomial space
PSPACE ⊆ EXPTIME	Proven	Polynomial-space configurations can be explored in exponential time
EXPTIME ⊆ EXPSPACE	Proven	Time bounds also bound space usage
P ≠ NP	Open	No known proof
NP ≠ PSPACE	Open	No known proof
PSPACE ≠ EXPTIME	Open	No known proof
EXPTIME ≠ EXPSPACE	Open	No known proof
P ≠ EXPTIME	Proven	Time Hierarchy Theorem
PSPACE ≠ EXPSPACE	Proven	Space Hierarchy Theorem

An important consequence is that at least one inclusion between P and EXPTIME must be strict:

P ⊊ E X P T I M E

Similarly, at least one inclusion between PSPACE, EXPTIME, and EXPSPACE must be strict.

However, current theory does not establish which adjacent inclusions are strict.

4. The Role of Complexity Hypotheses

Beyond unconditional theorems, complexity theory uses hypotheses to establish conditional lower bounds.

The Exponential Time Hypothesis (ETH) traditionally asserts that 3-SAT cannot be solved in subexponential time:

3 -SAT \notin D T I M E (2^{o (n)})

ETH is stronger than the assumption that P differs from NP. If ETH is false, however, this alone does not imply P = NP.

Crucially, the established separations P ≠ EXPTIME and PSPACE ≠ EXPSPACE do not depend on ETH. They remain valid regardless of the outcome of research concerning exponential-time algorithms for satisfiability.

5. Conclusion

Computational complexity theory provides a rigorous hierarchy of problems according to their time and memory requirements.

The inclusions

P \subseteq N P \subseteq P S P A C E \subseteq E X P T I M E \subseteq E X P S P A C E

are established mathematical facts, but the precise relationships between neighboring classes remain among the deepest open questions in theoretical computer science.

Two unconditional results provide important boundaries:

P \neq E X P T I M E

P S P A C E \neq E X P S P A C E

These theorems demonstrate that computational resources form genuine hierarchies, even though major questions about the relative power of time, space, and nondeterminism remain unresolved.

References

Hartmanis, J., & Stearns, R. E. (1965). On the computational complexity of algorithms. Transactions of the American Mathematical Society, 117, 285–306.
Savitch, W. J. (1970). Relationships between nondeterministic and deterministic tape complexities. Journal of Computer and System Sciences, 4(2), 177–192.
Arora, S., & Barak, B. (2009). Computational Complexity: A Modern Approach. Cambridge University Press.
Papadimitriou, C. H. (1994). Computational Complexity. Addison-Wesley.